//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
// 
//
// 示例 2： 
//
// 
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
// 
//
// 示例 3： 
//
// 
//输入：s = ""
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3 * 104 
// s[i] 为 '(' 或 ')' 
// 
// 
// 
// Related Topics 栈 字符串 动态规划 
// 👍 1424 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.util.LinkedList;

public class LongestValidParentheses {
    public static void main(String[] args) {
        Solution solution = new LongestValidParentheses().new Solution();
        System.out.println(solution.longestValidParentheses("(()"));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestValidParentheses(String s) {
        LinkedList<Integer> stack = new LinkedList<>();
        int maxCount = 0;
        // 有效括号开始下标
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            switch (cur){
                case '(':
                    stack.addLast(i);
                    continue;
                case ')':
                    if (!stack.isEmpty() && s.charAt(stack.getLast())=='('){
                        stack.pollLast();
                        // 匹配顺利，栈内无残留，则i-start+1进行更新
                        if (stack.isEmpty()) {
                            maxCount = Math.max(maxCount, i-start+1);
                        // 匹配顺利，栈内有残留，无法保证栈内剩余左括号可以被成功匹配，只能保证i-stack.getLast()
                        }else {
                            maxCount = Math.max(maxCount,i-stack.getLast());
                        }
                    }else {
                        // 遇到")"则更新有效括号开始下标
                        start=i+1;
                    }
                    continue;
            }
        }
        return maxCount;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}